πŸ‘©β€πŸ’» 16172. λ‚˜λŠ” μΉœκ΅¬κ°€ 적닀(Large)

@Seongukbaek Posted May 28, 2022 Β· Updated May 28, 2022 Β· 2 min read

문제

BOJ - λ‚˜λŠ” μΉœκ΅¬κ°€ 적닀(Large)

πŸ“ Logic

πŸ“„ CODE

μ½”λ“œ 보기/μ ‘κΈ°πŸ’«
import java.io.*; import java.util.Stack; import java.util.regex.Matcher; import java.util.regex.Pattern; class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String book = br.readLine().replaceAll("\\d", ""); String keyword = br.readLine(); System.out.println(KMP(book, keyword) ? 1 : 0); } public static int[] computeTable(String book) { int n = book.length(); int[] table = new int[n]; int idx = 0; for (int i = 1; i < n; i++) { // λ¬Έμžκ°€ μΌμΉ˜ν•˜λ©΄, μ—°μ†μ μœΌλ‘œ μΌμΉ˜ν•  λ•ŒκΉŒμ§€ 탐색 // μΌμΉ˜ν•˜μ§€ μ•ŠλŠ” 경우 이전 idx의 table값을 idx둜 while (idx > 0 && book.charAt(i) != book.charAt(idx)) idx = table[idx - 1]; if (book.charAt(i) == book.charAt(idx)) { idx += 1; table[i] = idx; } } return table; } public static boolean KMP(String book, String keyword) { int n1 = book.length(); int n2 = keyword.length(); int[] table = computeTable(book); boolean found = false; int idx = 0; // ν˜„μž¬ λŒ€μ‘λ˜λŠ” κΈ€μž 수 for(int i = 0; i < n1; i++) { // ν‚€μ›Œλ“œμ˜ idx번 κΈ€μžμ™€ κ΅κ³Όμ„œμ˜ ν•΄λ‹Ή κΈ€μžκ°€ λΆˆμΌμΉ˜ν•  경우, // ν˜„μž¬ λŒ€μ‘λœ κΈ€μžμ˜ 수λ₯Ό table[idx-1]번으둜 쀄인닀. while (idx > 0 && book.charAt(i) != keyword.charAt(idx)) idx = table[idx - 1]; // κΈ€μžκ°€ λŒ€μ‘λ  경우 if (book.charAt(i) == keyword.charAt(idx)) { if (idx == n2 - 1) { found = true; break; } else idx += 1; } } return found; } }

✏️ Review

  • μ •κ·œν‘œν˜„μ‹μœΌλ‘œ μ ‘κ·Όν–ˆλ‹€κ°€ μ—„μ²­λ‚œ μ‹œκ°„μ΄ˆκ³Όλ₯Ό 맞λ‹₯뜨렀 무슨 μ•Œκ³ λ¦¬μ¦˜μ„ μ“°λŠ”μ§€ λ΄€λ‹€.
  • KMP μ•Œκ³ λ¦¬μ¦˜μ€ 잘 μ΄ν•΄ν•˜μ§€ λͺ»ν•΄μ„œ 후에 λ‹€μ‹œ μ΄ν•΄ν•œ 후에 λ‘œμ§μ„ 적어봐야 ν•  것 κ°™λ‹€.
@Seongukbaek
배우고 μ •λ¦¬ν•˜κ³  κ³΅μœ ν•˜λŠ” λŒ€ν•™μƒ λ°±μ„±μš±μž…λ‹ˆλ‹€ πŸ˜€